import java.util.NoSuchElementException;

public class RealizationTree<E extends Comparable> implements ITree<E> {
	private Node<E> head;
	private int size;


	@Override
	public boolean add(E item) {
		size++;
		if ( head == null ) {
			head = new Node(item, null, null);
			return true;
		}
		return add(head, item);

	}

	@Override
	public void remove(E value) {
		head = remove(head, value);
	}

	private Node<E> remove(Node<E> element, E value) {
		if ( element == null )
			return null;
		if ( ! contains(head, value) ) {
			throw new NoSuchElementException("There is no such element in your Tree");
		}
		size--;
		int cmp = value.compareTo(element.value);
		if ( cmp < 0 ) {
			element.left = remove(element.left, value);
		} else if ( cmp > 0 ) {
			element.right = remove(element.right, value);
		} else {
			if ( element.left == null ) {
				return element.right;
			} else if ( element.right == null ) {
				return element.left;
			} else {
				Node<E> temp = element;
				element = min(temp.right);
				element.right = removeMin(element.right);
				element.left = temp.left;
			}
		}
		return element;
	}


	private Node<E> removeMin(Node<E> element) {
		if ( element == null ) {
			return null;
		} else if ( element.left == null ) {
			return element.right;
		} else {
			element.left = removeMin(element.left);
			return element;
		}
	}

	private Node<E> min(Node<E> element) {
		return (element.left == null) ? element : min(element.left);
	}


	private boolean add(Node<E> element, E value) {

		if ( (element.value).compareTo(value) >= 0 ) {
			if ( element.left == null ) {
				element.left = new Node(value, null, null);
				return true;
			} else {
				add(element.left, value);
			}
		} else {
			if ( element.right == null ) {
				element.right = new Node(value, null, null);
				return true;
			} else {
				add(element.right, value);
			}
		}
		return true;
	}


	@Override
	public boolean contains(E value) {
		return contains(head, value);
	}

	private boolean contains(Node<E> element, E value) {
		if ( element.value.equals(value) ) {
			return true;
		} else if ( (element.value).compareTo(value) >= 0 && element.left != null ) {
			return contains(element.left, value);
		} else {
			if ( element.right != null ) {
				return contains(element.right, value);
			}
		}
		return false;
	}


	@Override
	public E search(E value) {
		if ( value == null ) {
			throw new IllegalArgumentException("argument mustn't be null");
		} else if ( head.value.compareTo(value) == 0 ) {
			return head.value;
		} else return search(head, value).value;
	}


	private Node<E> search(Node<E> element, E value) {

		if ( element.value.compareTo(value) > 0 ) {
			if ( element.left != null ) {
				if ( element.left.value.equals(value) ) {
					return element;
				} else {
					return search(element.left, value);
				}
			} else {
				throw new NoSuchElementException();
			}
		} else {
			if ( element.right != null ) {
				if ( element.right.value.equals(value) ) {
					return element;
				} else {
					return search(element.right, value);
				}
			} else {
				throw new NoSuchElementException();
			}

		}

	}

	@Override
	public int size() {
		return size;
	}

	@Override
	public void clear() {
		head = null;
		size = 0;
	}

	@Override
	public void printWidth() {
		printWidth(head, 0);
	}

	private void printWidth(Node<E> element, int depth) {
		if ( element != null ) {
			printWidth(element.right, depth + 1);
			for ( int k = 0; k < depth; k++ ) {
				System.out.print("    ");
			}
			System.out.println(element.value);
			printWidth(element.left, depth + 1);
		}
	}

	@Override
	public void printDeep() {
		if ( head != null ) {
			System.out.println(printDeep(head));
		}
	}

	private String printDeep(Node element) {
		if ( element != null ) {
			return element.value.toString() + " " + printDeep(element.left) + printDeep(element.right);
		}
		return "";

	}


	//Element of Tree
	private class Node<E> {
		private E value;
		private Node<E> left;
		private Node<E> right;

		private Node(E value, Node<E> left, Node<E> right) {
			this.value = value;
			this.left = left;
			this.right = right;
		}
	}
}
